package com.cyan.learn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * 数组算法
 */
public class ArrayTest {

    /**
     * 二分法实现
     */
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }

        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }

        int left = 0;
        int right = nums.length - 1;
        int mid;

        return -1;
    }

    /**
     * 27丶移除元素
     * 双指针，快慢指针
     */
    public int removeElement(int[] nums, int val) {
        int left, right;
        for (left = 0, right = 0; right < nums.length; right++) {
            if (nums[right] != val) {
                nums[left++] = nums[right];
            }
        }

        return left;
    }

    /**
     * 977丶有序数组的平方
     * 双指针，左右指针
     */
    public int[] sortedSquares(int[] nums) {
        int[] newArr = new int[nums.length];

        int left = 0;
        int right = nums.length - 1;
        int k = nums.length - 1;

        while (left <= right) {
            if (Math.abs(nums[left]) < Math.abs(nums[right])) {
                newArr[k--] = nums[right] * nums[right];
                right--;
            } else {
                newArr[k--] = nums[left] * nums[left];
                left++;
            }
        }

        return newArr;
    }

    /**
     * 209丶长度最小的子数组
     * 双指针，滑动窗口
     */
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0;
        int right;
        int left = 0;
        int minLen = Integer.MAX_VALUE;

        for (right = 0; right < nums.length; right++) {
            sum += nums[right];

            if (sum >= target) {
                while (sum >= target) {
                    minLen = Math.min(minLen, right - left + 1);
                    sum -= nums[left++];
                }
            }
        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    /**
     * 1、两数之和
     */
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{i, map.get(target - nums[i])};
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }

    /**
     * 4、两个正序整数的中位数
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] arr = new int[len1 + len2];

        int i = 0, j = 0, k = 0;
        while (i < len1 && j < len2) {
            if (nums1[i] < nums2[j]) {
                arr[k] = nums1[i++];
            } else {
                arr[k] = nums2[j++];
            }
            k++;
        }

        if (i == len1) {
            while (j < len2) {
                arr[k++] = nums2[j++];
            }
        }
        if (j == len2) {
            while (i < len1) {
                arr[k++] = nums1[i++];
            }
        }

        // 奇数偶数
        if (arr.length % 2 == 0) {
            return (double) (arr[arr.length / 2] + arr[arr.length / 2 - 1]) / 2;
        } else {
            return arr[arr.length / 2];
        }
    }

    /**
     * 11、盛水最多的容器
     */
    public int maxArea(int[] height) {
        // 左右指针
        int left = 0, right = height.length - 1;
        int max = 0;

        while (left < right) {
            int min = Math.min(height[left], height[right]);
            max = Math.max((right - left) * min, max);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }

    /**
     * 15、三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int target = -nums[i]; // 固定一个数，然后转为两数之和解法

            HashMap<Integer, Integer> map = new HashMap<>();
            for (int j = i + 1; j < nums.length; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                if (map.containsKey(target - nums[j])) {
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[j]);
                    item.add(target - nums[j]);
                    list.add(item);
                } else {
                    map.put(nums[j], j);
                }
            }
        }

        return list;
    }
}